import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description: 二叉树的基本操作
 * User: 86187
 * Date: 2022-08-01
 * Time: 14:31
 */

public class BinaryTree {
    static class TreeNode {
        public char val;
        public TreeNode left;  //左孩子
        public TreeNode right;  //右孩子
        public TreeNode(char val) {
            this.val = val;
        }
    }

    public TreeNode root;

    public void createTree() { //穷举法创建二叉树
                                            //
        TreeNode A = new TreeNode('A'); //                A
        TreeNode B = new TreeNode('B'); //
        TreeNode C = new TreeNode('C'); //         B            C
        TreeNode D = new TreeNode('D'); //
        TreeNode E = new TreeNode('E'); //     D      E      F      G
        TreeNode F = new TreeNode('F'); //
        TreeNode G = new TreeNode('G'); //  H(是D的左孩子)   I(是F的左孩子)
        TreeNode H = new TreeNode('H'); //
        TreeNode I = new TreeNode('I');
                                            //
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        D.left = H;
        F.left = I;
        this.root = A;
    }


    // 前序遍历：打印顺序:根 -> 左 -> 右
    void preOrder(TreeNode root) {
        if(root == null)
            return;
        System.out.print(root.val+" ");//先打印根节点
        preOrder(root.left);
        preOrder(root.right);
    }

    /**
    //前序遍历二叉树:力扣144题
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();

        if(root == null) return list;

        //list.add(Integer.parseInt(String.valueOf(root.val)));
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);

    }
*/

// 中序遍历：打印顺序:左 -> 根 -> 右
    void inOrder(TreeNode root) {
        if(root == null)
            return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }


// 后序遍历：打印顺序:左 -> 右 -> 根
    void postOrder(TreeNode root) {
        if(root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }


//层序遍历：
    //1.非递归实现:使用队列
    void levelOrder(TreeNode root) {
        if(root == null) return ;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();  //获取队头元素(出队)
            System.out.print(cur.val+" ");
            if(cur.left != null) {
                queue.offer(cur.left);
            }
            if(cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }

    /**
     * 分层遍历:给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。
     * @param root 根节点
     */
    public List<List<Character>> levelOrder2(TreeNode root) {
        //依赖于队列来做
        //如何判断哪些数据属于哪一层呢？？？

        List<List<Character>> ret = new ArrayList<>();
        if(root == null) { return ret; }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()) {

            int size = queue.size();
            List<Character> row = new ArrayList<>();
            while(size > 0) {
                TreeNode cur = queue.poll();  //获取队头元素(出队)
                size--;

                //System.out.print(cur.val+" ");
                row.add(cur.val);

                if(cur.left != null) {
                    queue.offer(cur.left);
                }
                if(cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            ret.add(row);
        }
        return ret;
    }

    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root) {
        if(root == null) return true;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();  //获取队头元素(出队)

            if(cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else {
                break;
            }
        }
        while (!queue.isEmpty()) {
            TreeNode cur = queue.peek();
            if(cur != null) {
                //不是满二叉树
                return false;
            }else {
                queue.poll();
            }
        }
        return true;
    }
    /**
     * 子问题思路 : 获取树中节点的个数
     * @param root 根节点
     * @return  节点个数
     */
    int size1(TreeNode root) {
        int size = 0;
        if(root == null)
            return 0;
        size++;
        size += size1(root.left);
        size += size1(root.right);
        return size;

        // 或者也可以直接这么写:
        //if(root == null)
        //    return 0;
        //return size1(root.left)+size(root.right)+1;
    }

    /**
     * 遍历思路:只要遍历到节点，size++
     */
    public static int size;
    int size2(TreeNode root) {
        if(root == null)
            return 0;
        size++;
        size2(root.left);
        size2(root.right);
        return size;
    }


    /**
     * 子问题思路:左树的叶子 + 右树的叶子 = 整棵树的叶子
     * @param root 根节点
     * @return  叶子节点的个数
     */
    int getLeafNodeCount1(TreeNode root) {
        if(root == null) { return 0;}

        if(root.left == null && root.right == null) {
            return 1;
        }

        return getLeafNodeCount1(root.left) + getLeafNodeCount1(root.right);
    }

    /**
     * 遍历思路 ：遍历到叶子就++
     */
    public static int leafSize;
    int getLeafNodeCount2(TreeNode root) {
        if(root == null) { return 0;}

        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);

        return leafSize;
    }



// 获取第K层节点的个数(假设k合法)
    int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null) { return 0; }

        if(k == 1) { return 1;}

        return getKLevelNodeCount(root.left,k-1)+ getKLevelNodeCount(root.right,k-1);
    }



// 获取二叉树的高度:时间复杂度 O(n)
    int getHeight(TreeNode root) {
        if(root == null) { return 0;}

        /*
         以下的写法不可取,重复遍历了，OJ题上可能会超出时间限制！！！
        return getHeight(root.left) > getHeight(root.right) ?
                getHeight(root.left) + 1 :
                getHeight(root.right) + 1;
         */
        //以上方法应写为:
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;

        //这是我推荐的写法
        //return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }



//给定一个二叉树，判断它是否是高度平衡的二叉树。
    //本题中，一棵高度平衡二叉树定义为：
    //      一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1
    //时间复杂度为:O(n^2)
    public boolean isBalanced(TreeNode root) {
        if(root == null) {return true;}

        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);

        return Math.abs(leftHeight - rightHeight) <= 1 &&
                isBalanced(root.right) && isBalanced(root.left);
    } //该题目时间复杂度太高，可改进为：：
    public int maxDepth(TreeNode root) {
        if(root == null) {return 0;}

        int leftHeight = maxDepth(root.left);
        int rightHeight = maxDepth(root.right);

        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {
            return Math.max(leftHeight,rightHeight) + 1;
        } else {
            return -1;
        }
    }
    public boolean isBalanced2(TreeNode root) {
        if(root == null) {return true;}

        return maxDepth(root) >= 0;
    } //改进后时间复杂度为O(n)



// 检测值为value的元素是否存在
    TreeNode find(TreeNode root, char val) {
        if(root == null) {return null;}

        if(root.val == val) {return root;}

        TreeNode ret = find(root.left,val);
        if(ret != null) { return ret;}

        TreeNode ret2 = find(root.right,val);
        if(ret2 != null) { return ret2;}

        return null;
    }


//检验这两棵树是否相同。
    //如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if((p != null && q == null) || (q != null && p == null)) {
            return false;
        }
        if(p == null && q == null) { return true; }
        if(p.val != q.val) { return false; }

        //走到这：p != null && q != null && p.val == q.val
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }


//给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。
    // 如果存在，返回 true ；否则，返回 false 。
    //假设root节点数为n subRoot节点数为m 则时间复杂度为 O(n*m)
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //1.先判断当前subRoot和root是不是相同的两棵树
        //2.如果不是，则判断subRoot是不是root.left的子树
        //3.是不是root.left的子树？也是需要判断root.left是不是和subRoot是两颗相同的树

        if(root == null) { return false;}

        if(isSameTree(root,subRoot)) {return true;}

        if(isSubtree(root.left,subRoot)) {return true;}

        if(isSubtree(root.right,subRoot)) {return true;}

        return false;
    }



//给你一个二叉树的根节点 root ， 检查它是否轴对称(力扣 101 题)
    public boolean isSymmetric(TreeNode root) {
        if(root == null) { return true; }

        return isSymmetricChild(root.left,root.right);
    }
    private boolean isSymmetricChild(TreeNode leftTree,TreeNode rightTree) {
        //判断root的左树和右树是否对称
        if(leftTree != null && rightTree == null || rightTree != null && leftTree == null) {
            return false;
        }

        if(leftTree == null && rightTree == null) { return true; }
        if(leftTree.val != rightTree.val) { return false; }

        return isSymmetricChild(leftTree.left,rightTree.right) &&
                isSymmetricChild(leftTree.right,rightTree.left);
    }



}
